package com.data_structure_algorithm.algorithm;

/**
 * @Authror PABLO
 * @Date 2022/4/7 22:29
 * @Desc
 */
public class NQueen {
    public static void main(String[] args) {
        int n = 2 << 2;
        int[] arr = new int[n];

        int num = put(arr);
        System.out.println(num);
    }

    private static int put(int[] arr) {

        //皇后个数n
        int n = arr.length;
        //数组下标代表行,从0开始
        int index = 0;

        return process(arr, index, n);

    }

    private static int process(int[] arr, int index, int n) {

        //如果顺利走到最后，说明探索到了一种方式
        if (index == n) {
            return 1;
        }
        int result = 0;
        //index还没走到最后，每摆放一个，需要回溯检查,判断col和以前的是否有冲突
        for (int col = 0; col < arr.length; col++) {
            if (check(arr, index, col)) {  //  index当前行的col列，回溯冲突
                //摆放
                arr[index] = col;
                result += process(arr, index + 1, n);
            }
        }
        return result;
    }

    /**
     * @Description:
     * @Author: PABLO
     * @Date: 2022/4/7 22:55
     * @Params: [arr, index 当前摆放的行, col 当前检查的列的值，每次摆放都检查以前放过的列]
     * @Return: boolean
     **/
    private static boolean check(int[] arr, int index, int col) {

        //检查当前摆放位置和之前是否有冲突
        //一维数组，每个元素代表行，数值代表列
        //只需要检查列
        for (int i = 0; i < index; i++) {
            //i代表index之前摆放的列
            if (col == arr[i] || Math.abs(index - i) == Math.abs(col - arr[i])) return false;
        }
        return true;
    }
}
